#breadth first search pseudocode

[codezclub]

C Program to implement BFS Algorithm for Connected Graph

BFS Algorithm for Connected Graph Write a C Program to implement BFS Algorithm for Connected Graph. Here’s simple Program for traversing a directed graph through Breadth First Search(BFS),  visiting only those vertices that are reachable from start vertex. Breadth First Search (BFS) BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and…

[viswatechynology]

BFS Algorithm

Breadth-First Search Algorithm

Breadth-First Search Algorithm or BFS is the most widely utilized method.

BFS is a graph traversal approach in which you start at a source node and layer by layer through the graph, analyzing the nodes directly related to the source node. Then, in BFS traversal, you must move on to the next-level neighbor nodes.

According to the BFS, you must traverse the graph in a breadthwise direction:

· To begin, move horizontally and visit all the current layer’s nodes.

· Continue to the next layer.

Breadth-First Search uses a queue data structure to store the node and mark it as “visited” until it marks all the neighboring vertices directly related to it. The queue operates on the First In First Out (FIFO) principle, so the node’s neighbors will be viewed in the order in which it inserts them in the node, starting with the node that was inserted first.

Read More

Why Do You Need Breadth-First Search Algorithm?

There are several reasons why you should use the BFS Algorithm to traverse graph data structure. The following are some of the essential features that make the BFS algorithm necessary:

· The BFS algorithm has a simple and reliable architecture.

· The BFS algorithm helps evaluate nodes in a graph and determines the shortest path to traverse nodes.

· The BFS algorithm can traverse a graph in the fewest number of iterations possible.

· The iterations in the BFS algorithm are smooth, and there is no way for this method to get stuck in an infinite loop.

· In comparison to other algorithms, the BFS algorithm’s result has a high level of accuracy.

In this tutorial, next, you will look at the pseudocode for the breadth-first search algorithm.

Pseudocode Of Breadth-First Search Algorithm

The breadth-first search algorithm’s pseudocode is:

Read More

Bredth_First_Serach( G, A ) // G ie the graph and A is the source node

Let q be the queue

q.enqueue( A ) // Inserting source node A to the queue

Mark A node as visited.

While ( q is not empty )

B = q.dequeue( ) // Removing that vertex from the queue, which will be visited by its neighbour

Processing all the neighbors of B

For all neighbors of C of B

If C is not visited, q. enqueue( C ) //Stores C in q to visit its neighbour

Mark C a visited

For a better understanding, you will look at an example of a breadth-first search algorithm later in this tutorial.

Example of Breadth-First Search Algorithm

In a tree-like structure, graph traversal requires the algorithm to visit, check, and update every single un-visited node. The sequence in which graph traversals visit the nodes on the graph categorizes them.

The BFS algorithm starts at the first starting node in a graph and travels it entirely. After traversing the first node successfully, it visits and marks the next non-traversed vertex in the graph.

Step 1: In the graph, every vertex or node is known. First, initialize a queue.

Step 2: In the graph, start from source node A and mark it as visited.

Step 3: Then you can observe B and E, which are unvisited nearby nodes from A. You have two nodes in this example, but here choose B, mark it as visited, and enqueue it alphabetically.

Step 4: Node E is the next unvisited neighboring node from A. You enqueue it after marking it as visited.

Step 5: A now has no unvisited nodes in its immediate vicinity. As a result, you dequeue and locate A.

Read More

Step 6: Node C is an unvisited neighboring node from B. You enqueue it after marking it as visited.

Step 7: Node D is an unvisited neighboring node from C. You enqueue it after marking it as visited.

Step 8: If all of D’s adjacent nodes have already been visited, remove D from the queue.

Step 9: Similarly, all nodes near E, B, and C nodes have already been visited; therefore, you must remove them from the queue.

Step 10: Because the queue is now empty, the bfs traversal has ended.

Complexity Of Breadth-First Search Algorithm

The time complexity of the breadth-first search algorithm : The time complexity of the breadth-first search algorithm can be stated as O(|V|+|E|) because, in the worst case, it will explore every vertex and edge. The number of vertices in the graph is |V|, while the edges are |E|.

The space complexity of the breadth-first search algorithm : You can define the space complexity as O(|V|), where |V| is the number of vertices in the graph, and different data structures are needed to determine which vertices have already been added to the queue. This is also the space necessary for the graph, which varies depending on the graph representation used by the algorithm’s implementation.

You will see some bfs algorithm applications now that you’ve grasped the complexity of the breadth-first search method.

Application Of Breadth-First Search Algorithm

The breadth-first search algorithm has the following applications:

· For Unweighted Graphs, You Must Use the Shortest Path and Minimum Spacing Tree.

Read More

The shortest path in an unweighted graph is the one with the fewest edges. You always reach a vertex from a given source using the fewest amount of edges when utilizing breadth-first. In unweighted graphs, any spanning tree is the Minimum Spanning Tree, and you can identify a spanning tree using either depth or breadth-first traversal.

· Peer to Peer Network

Breadth-First Search is used to discover all neighbor nodes in peer-to-peer networks like BitTorrent.

· Crawlers in Search Engine

Crawlers create indexes based on breadth-first. The goal is to start at the original page and follow all of the links there, then repeat. Crawlers can also employ Depth First Traversal. However, the benefit of breadth-first traversal is that the depth or layers of the created tree can be limited.

· Social Networking Websites

You can use a breadth-first search to identify persons within a certain distance ‘d’ from a person in social networks up to ‘d’s levels.

· GPS Navigation System

To find all nearby locations, utilize the breadth-first search method.

· Broadcasting Network

A broadcast packet in a network uses breadth-first search to reach all nodes.

· Garbage Collection

Cheney’s technique uses the breadth-first search for duplicating garbage collection. Because of the better locality of reference, breadth-first search is favored over the Depth First Search algorithm.

· Cycle Detection in Graph

Cycle detection in undirected graphs can be done using either Breadth-First Search or Depth First Search. BFS can also be used to find cycles in a directed graph.

· Identifying Routes

To see if there is a path between two vertices, you can use either Breadth-First or Depth First Traversal.

· Finding All Nodes Within One Connected Component

To locate all nodes reachable from a particular node, you can use either Breadth-First or Depth First Traversal.

Read More

Code Implementation of Breadth-First Search Algorithm

Breadth-First Search Algorithm Code Implementation:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int twodimarray[10][10],queue[10],visited[10],n,i,j,front=0,rear=-1;

void breadthfirstsearch(int vertex) // breadth first search function

{

for (i=1;i<=n;i++)

if(twodimarray[vertex][i] && !visited[i])

queue[++rear]=i;

if(front<=rear)

{

visited[queue[front]]=1;

breadthfirstsearch(queue[front++]);

}

}

int main() {

int x;

printf(“\n Enter the number of vertices:”);

scanf(“%d”,&n);

for (i=1;i<=n;i++) {

queue[i]=0;

visited[i]=0;

}

printf(“\n Enter graph value in form of matrix:\n”);

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

scanf(“%d”,&twodimarray[i][j]);

printf(“\n Enter the source node:”);

scanf(“%d”,&x);

breadthfirstsearch(x);

printf(“\n The nodes which are reachable are:\n”);

for (i=1;i<=n;i++)

if(visited[i])

printf(“%d\t”,i);

else

printf(“\n Breadth first search is not possible”);

getch();

}

[viswatech]

BFS Algorithm

Breadth-First Search Algorithm

Breadth-First Search Algorithm or BFS is the most widely utilized method.

BFS is a graph traversal approach in which you start at a source node and layer by layer through the graph, analyzing the nodes directly related to the source node. Then, in BFS traversal, you must move on to the next-level neighbor nodes.

According to the BFS, you must traverse the graph in a breadthwise direction:

·         To begin, move horizontally and visit all the current layer's nodes.

·         Continue to the next layer.

 Breadth-First Search uses a queue data structure to store the node and mark it as "visited" until it marks all the neighboring vertices directly related to it. The queue operates on the First In First Out (FIFO) principle, so the node's neighbors will be viewed in the order in which it inserts them in the node, starting with the node that was inserted first.

Read More

Why Do You Need Breadth-First Search Algorithm? 

There are several reasons why you should use the BFS Algorithm to traverse graph data structure. The following are some of the essential features that make the BFS algorithm necessary:

·         The BFS algorithm has a simple and reliable architecture.

·         The BFS algorithm helps evaluate nodes in a graph and determines the shortest path to traverse nodes.

·         The BFS algorithm can traverse a graph in the fewest number of iterations possible.

·         The iterations in the BFS algorithm are smooth, and there is no way for this method to get stuck in an infinite loop.

·         In comparison to other algorithms, the BFS algorithm's result has a high level of accuracy.

In this tutorial, next, you will look at the pseudocode for the breadth-first search algorithm.

Pseudocode Of Breadth-First Search Algorithm 

The breadth-first search algorithm's pseudocode is:

Read More

Bredth_First_Serach( G, A ) // G ie the graph and A is the  source node

          Let  q be the queue 

          q.enqueue(  A ) // Inserting source node A to the queue

          Mark  A node as visited.

          While  ( q is not empty )

          B  = q.dequeue( ) // Removing that vertex from the queue, which will be visited  by its neighbour

Processing all the neighbors of B

For all neighbors of C of B

             If  C is not visited, q. enqueue( C ) //Stores C in q to visit its neighbour

Mark C a visited

For a better understanding, you will look at an example of a breadth-first search algorithm later in this tutorial.

Example of Breadth-First Search Algorithm

In a tree-like structure, graph traversal requires the algorithm to visit, check, and update every single un-visited node. The sequence in which graph traversals visit the nodes on the graph categorizes them.

The BFS algorithm starts at the first starting node in a graph and travels it entirely. After traversing the first node successfully, it visits and marks the next non-traversed vertex in the graph.

Step 1: In the graph, every vertex or node is known. First, initialize a queue.

 Step 2: In the graph, start from source node A and mark it as visited.

 Step 3: Then you can observe B and E, which are unvisited nearby nodes from A. You have two nodes in this example, but here choose B, mark it as visited, and enqueue it alphabetically.

 Step 4: Node E is the next unvisited neighboring node from A. You enqueue it after marking it as visited.

 Step 5: A now has no unvisited nodes in its immediate vicinity. As a result, you dequeue and locate A.

 Read More

Step 6: Node C is an unvisited neighboring node from B. You enqueue it after marking it as visited.

 Step 7: Node D is an unvisited neighboring node from C. You enqueue it after marking it as visited.

 Step 8: If all of D's adjacent nodes have already been visited, remove D from the queue.

 Step 9: Similarly, all nodes near E, B, and C nodes have already been visited; therefore, you must remove them from the queue.

 Step 10: Because the queue is now empty, the bfs traversal has ended.

Complexity Of Breadth-First Search Algorithm

The time complexity of the breadth-first search algorithm : The time complexity of the breadth-first search algorithm can be stated as O(|V|+|E|) because, in the worst case, it will explore every vertex and edge. The number of vertices in the graph is |V|, while the edges are |E|.

The space complexity of the breadth-first search algorithm : You can define the space complexity as O(|V|), where |V| is the number of vertices in the graph, and different data structures are needed to determine which vertices have already been added to the queue. This is also the space necessary for the graph, which varies depending on the graph representation used by the algorithm's implementation.

You will see some bfs algorithm applications now that you’ve grasped the complexity of the breadth-first search method.

Application Of Breadth-First Search Algorithm 

The breadth-first search algorithm has the following applications:

·         For Unweighted Graphs, You Must Use the Shortest Path and Minimum Spacing Tree.

Read More

The shortest path in an unweighted graph is the one with the fewest edges. You always reach a vertex from a given source using the fewest amount of edges when utilizing breadth-first. In unweighted graphs, any spanning tree is the Minimum Spanning Tree, and you can identify a spanning tree using either depth or breadth-first traversal.

·         Peer to Peer Network

Breadth-First Search is used to discover all neighbor nodes in peer-to-peer networks like BitTorrent.

·         Crawlers in Search Engine

Crawlers create indexes based on breadth-first. The goal is to start at the original page and follow all of the links there, then repeat. Crawlers can also employ Depth First Traversal. However, the benefit of breadth-first traversal is that the depth or layers of the created tree can be limited.

·         Social Networking Websites

You can use a breadth-first search to identify persons within a certain distance 'd' from a person in social networks up to 'd's levels.

·         GPS Navigation System

To find all nearby locations, utilize the breadth-first search method.

·         Broadcasting Network 

A broadcast packet in a network uses breadth-first search to reach all nodes.

·         Garbage Collection 

Cheney's technique uses the breadth-first search for duplicating garbage collection. Because of the better locality of reference, breadth-first search is favored over the Depth First Search algorithm.

·         Cycle Detection in Graph

Cycle detection in undirected graphs can be done using either Breadth-First Search or Depth First Search. BFS can also be used to find cycles in a directed graph.

·         Identifying Routes

To see if there is a path between two vertices, you can use either Breadth-First or Depth First Traversal.

·         Finding All Nodes Within One Connected Component

To locate all nodes reachable from a particular node, you can use either Breadth-First or Depth First Traversal.

Read More

Code Implementation of Breadth-First Search Algorithm 

Breadth-First Search Algorithm Code Implementation:

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int  twodimarray[10][10],queue[10],visited[10],n,i,j,front=0,rear=-1;

void breadthfirstsearch(int vertex) //  breadth first search function

{

for (i=1;i<=n;i++)

if(twodimarray[vertex][i] &&  !visited[i])

queue[++rear]=i;

if(front<=rear)

{

visited[queue[front]]=1;

breadthfirstsearch(queue[front++]);

}

}

int main() {

int x;

printf("\n Enter the number of  vertices:");

scanf("%d",&n);

for (i=1;i<=n;i++) {

queue[i]=0;

visited[i]=0;

}

printf("\n Enter graph value in form of  matrix:\n");

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

scanf("%d",&twodimarray[i][j]);

printf("\n Enter the source  node:");

scanf("%d",&x);

breadthfirstsearch(x);

printf("\n The nodes which are  reachable are:\n");

for (i=1;i<=n;i++)

if(visited[i])

printf("%d\t",i);

      else

printf("\n Breadth first search is not  possible");

getch();

}

[essayyard-blog]

Programming Question Part 1ProblemDevelop a simple Python program to demonstrate understanding of using the

New Post has been published on https://www.essayyard.com/programming-question-part-1problemdevelop-a-simple-python-program-to-demonstrate-understanding-of-using-the/

Programming Question Part 1ProblemDevelop a simple Python program to demonstrate understanding of using the

Part 1ProblemDevelop a simple Python program to demonstrate understanding of using the Tkinter module to design a simple widget and configure it using the layout manager. Then add an event handler that will accept text input to the button and display the content of the text when using the mouse to click on the “click here” button.The program must have the following:Documentation Guidelines:Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the ” angle brackets are only placeholders. You should replace the placeholders and the comments between them with your specific information). Your cover sheet should have some of the same information, but what follows should be at the top of each program’s sheet of source code. Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose. Be brief and to the point. Start your design by writing comment lines of pseudocode. Once that is complete, begin adding executable lines. Finally run and test your program.Deliverable(s):Your deliverable should be a Word document with screenshots showing the source code and running results, and discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.part 2For this assignment, you will develop working examples of a graphical user interface (GUI) and event handling and that demonstrate the following:Be sure to include a brief narrative of your code where you explain what the code is doing.Documentation Guidelines:Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the ” angle brackets are only placeholders. You should replace the placeholders and the comments between them with your specific information). Your cover sheet should have some of the same information, but what follows should be at the top of each program’s sheet of source code. Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose. Be brief and to the point. Start your design by writing comment lines of pseudocode. Once that is complete, begin adding executable lines. Finally run and test your program.Deliverable(s):Your deliverable should be a Word document with screenshots showing the GUI and event handling you have created. Also, discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.Part 3Write a Python program using the Python IDE based on recursion with trees that is both depth first and breadth first searches.The Python program to be developed will demonstrate the use of both depth-first (DFS) and breadth-first (BFS) searches. A tree node structure will be developed that will be used both for DFS and BFS searches. The program will apply recursion both for the DFS and BFS searches to completion of the entire DFS and BFS. Also, the Python program will provide as output some of the intermediate nodes that are transverse during the execution of the DFS and BFS. This output of the intermediate nodes searched will demonstrate the different paths executed during a DFS versus BFS.ProblemDevelop functions to demonstrate understanding of implementing a recursive depth first search (DFS) and an iterative breadth first search (BFS) in Python using a simple graph made of nodes. This example will use nodes A, B, C, D, and E connected as follows: A —– / | B-D-C | | / | E —–The program must have the following:Documentation Guidelines:Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the ” angle brackets are only placeholders. You should replace the placeholders and the comments between them with your specific information). Your cover sheet should have some of the same information, but what follows should be at the top of each program’s sheet of source code. Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose. Be brief and to the point. Start your design by writing comment lines of pseudocode. Once that is complete, begin adding executable lines. Finally run and test your program.Deliverable(s):Your deliverable should be a Word document with screenshots showing the source code and running results, and discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.Part 4Two user-defined classes are recommended: class Transaction, and class BankStatement. A main() function will be required that declares a BankStatement object and Transaction objects and then performs operations as shown in the example driver main function below. The BankStatement object (called myStatement in the example main() shown later) contains a container of Transaction objects along with other record-keeping data fields. This is yet another example of the Containment/Composition (a.k.a., “Has-A”) relationship that can exist between classes/objects.The Transaction class is used to create deposit and withdrawal objects. It contains a constructor for initialization. This constructor has three defaulted parameters to facilitate the user declaring transactions and passing appropriate initial data member values as parameters to this constructor or accepting one or more of its defaulted initializer values. It is certainly legal, and perhaps desirable, to also have a LoadTransaction() method that would take inputs from the keyboard on an interactive basis. This, in conjunction with a menu, is a desirable addition but not required for this exercise. The main() driver function shows a partial batch (i.e., hard-coded) implementation rather than the, perhaps, more desirable interactive implementation. See your instructor for any specific additional requirements.# Python model of a bank transaction which can be either# A deposit or a withdraw## Filename: transaction.pyclass Transaction: def __init__(self, inAmount = 0.0, inCode = ‘D’, inNote = “No note”): self.__Amount = inAmount if inAmount >= 0.0 else 0.0 self.__Code = inCode if inCode == ‘D’ or inCode == ‘W’ else ‘D’ self.__Note = inNote if len(inNote) > 0 else “No note” def setAmount(self, newAmount): self.__Amount = newAmount if newAmount >= 0.0 else self.__Amount def getAmount(self): return self.__Amount def setCode(self, newCode): self.__Code = newCode if newCode == ‘W’ or newCode == ‘D’ else self.__Code def getCode(self): return self.__Code def setNote(self, newNote): self.__Note = newNote if len(newNote) > 0 else self.__Note def getNote(self): return self.__Note def loadTransaction(self): self.setAmount(float(input(“Enter transaction amount(DD.CC), $ “))) self.setCode(input(“Enter transaction code (‘W’ or ‘D’), “)) self.setNote(input(“Enter purpose of transaction, “))The BankStatement class contains two list containers of Transaction objects, a list container of float values, some BankStatement support data fields, and the required methods to manipulate selected data fields, insert transactions, arrange (i.e., sort) the contained transaction objects, and print them.# Python model of a bank statement capable of# holding and managing multiple bank transactions## Filename: bankStatement.pyfrom transaction import Transactionclass BankStatement: def __init__(self, begBal = 0.0, endBal = 0.0): self.__TransactionLog = [] self.__ArrangedLog = [] self.__RunningBalLog = [] self.__BegBal = begBal self.__EndBal = endBal self.__NumEntries = 0 self.__NumDeposits = 0 self.__NumWithdrawals = 0 def setBegEndBals(self, balance): self.__BegBal = self.__EndBal = balance def getBegBal(self): return self.__BegBal def getEndBal(self): return self.__EndBal def getNumEntries(self): return self.__NumEntries def getNumDeposits(self): return self.__NumDeposits def getNumWithdrawals(self): return self.__NumWithdrawals def insertTransaction(self, transaction): self.__Transactionlog.append(transaction) # Update __RunningBalLog, increment __NumEntries and increment either # __NumDeposits or __NumWithdrawals depending upon whether transaction is a deposit # or a withdrawal def displayResults(self): # Displays __BegBal, __TransactionLog list, __RunningBal list, and final stats (i.e., __EndBal, total transactions, number of deposits and number of withdrawls) # See example output def arrangeTransactions(self): # Builds __ArrangedLog list from __TransactionLog list def printArranged(self): # Displays the __ArrangedLog listThe declared classes and their contents are a starting point for the program. You may not need all the class members described above. Do not feel bound to implement this program using the exact methods and/or data fields given. The primary objective is for you to solve the problem of providing a bank statement to the bank’s customers using O-O programming techniques. HOWEVER, if you deviate from the above design be sure to fully document your design! If in doubt as to whether your deviation violates the intent of this exercise, ask your instructor.In the interest of sound software engineering practice, make sure to validate the values provided to the constructor method of class BankStatement. For invalid values you may choose to completely reject the passed in values and set the data fields to some default (but valid) values. In either case you should also display an error message.Below is a non-interactive(i.e., batch), main driver test function that will confirm to you and your instructor that the program operates as expected. Use the transaction objects given as data for your final submission of the program.def main(): # NOTE THIS IS A NON-INTERACTIVE DRIVER! myStatement = BankStatement() myStatement.setBegEndBals(15.92); # Sets beginning AND ending balance data fields # Declare some transaction objects T1 = Transaction() # TEST DATA T1.setAmount (123.56) T1.setCode(‘D’) T1.setNote(“CTPay”) T2 = Transaction(153.86, ‘W’,”Rent”) T3 = Transaction() T3.setAmount(75.56) T3.setCode(‘D’) T3.setNote(“Tips”) T4 = Transaction(12.56, ‘D’,”Gift”) T5 = Transaction() T5.setAmount(73.74) T5.setCode(‘W’) T5.setNote(“Date”) T6 = Transaction(145.75, ‘D’,”Loan”) T7 = Transaction() T7.setAmount(40.00) T7.setCode(‘W’) T7.setNote(“Loan Payment”) T8 = Transaction(21.74, ‘W’, “Groceries”) # Now insert the transaction objects into the bank statement myStatement.enterTransaction(T1) # Enter transactions into the myStatement.enterTransaction(T2) # BankStatement object # Six more transactions entered…………………………………………………………… ……………………………………………………………………………………………… # continue # Manipulate the bank statement myStatement.displayResults() myStatement.arrangeTransactions() myStatement.printArranged()The following is a look at what the output might look like from the method, displayResults(). The beginning balance was: $15.92 Transaction: 1 was a D amount: $123.56 for CTPay Running Bal: $139.48 Transaction: 2 was a W amount: $153.86 for Rent Running Bal: $-14.38 OVERDRAWN etc., for the other transactions……….…………………………………………………… …….………………………………………………………………………………………. The ending balance is: $84.01 The number of Transactions is: 8 The number of Deposits is: 4 The number of Withdrawals is: 4The following is the result after calling the arrangeTransactions() and printArranged() methods in the BankStatement class. Printing the Deposits and Withdrawals as a group: Transaction was a D amount: $123.56 for CTPay Transaction was a D amount: $75.56 for Tips Transaction was a D amount: $12.56 for Gift Transaction was a D amount: $145.75 for Loan Transaction was a W amount: $153.86 for Rent Transaction was a W amount: $73.74 for Date Transaction was a W amount:$40.00 for Loan Payment Transaction was a W amount: $21.74 for GroceriesTo build the ArrangedLog container in method, arrangeTransactions(), the following strategy is recommended: 1. Traverse the TransactionLog container checking each cell to determine if it is a deposit (‘D’) or withdrawal (‘W’): Loop for number of entries in the TransactionLog if TransactionLog[i].getCode() == ‘D’: append transaction in TransactionLog[i] to next open cell in list container, ArrangedLog 2. In another loop (very similar to the loop above), go back to the beginning of the TransactionLog container and check for all the ‘W’s and copy (i.e., append) them to the ArrangedLog container following the deposits.Now the method, printArranged(), just needs to loop through its entries and display the contents of the ArrangedLog container as shown above.Notice that the methods of an object contained within a containment object are accessed with the selection operator just as though you had the name of the object. However, inside the BankStatement object (myStatement), all you have access to is a container of Transaction objects — not their individual names — hence the TransactionLog[i].getNote() notation.Deliverable(s)Your deliverable should be a Word document with screenshots showing the source code and running results. If the source code is too long, you may insert your source code files as Packages into the Word document. You may also login to the class by using a browser in the AWS, and upload your source code directly. Submit a cover sheet with the hardcopy of your work.

[kracekumar]

Grokking algorithm: Book Review

Grokking algorithm - An illustrated guide for programmers and other curious people is the book by Aditya Y. Bhargava about understanding algorithms. The book is different from other algorithm books. The book explains the chosen concepts with illustrated guide like cartoons, xkcd and doesn't let the followers lost in the sea of mathematical formulas or procedure.

The book discusses a handful of foundational topics on algorithms like Big O notation, Binary Search, Sorting, Recursion, Hash Tables, graphs, greedy algorithm, dynamic programming. Here is the link to Table Of Contents. The book is straightforward and easy to follow. The pictures with detailed walkthrough make learning algorithm fun; lively and joyous. The book covers multiple worked out (pictures!) problems for harder concepts like Breadth-first search and knapsack problems.

Here is a picture, solution for a knapsack problem. Consider you're a robber(I know you aren't one in real life) and broke into a store with a knapsack capacity 4lbs(No metric system :-(). There are three items stereo, laptop, guitar of different weight and worth. Come up with an algorithm to steal maximum valuable elements that fit in the knapsack.

Here is how worked out solution looks

If you are aware of dynamic programming, explanation, pseudocode may fit on a page, or two and solution in Python programming language may have 50 lines. The worked out solution spans across nine pages with detailed steps and data structures progression at each step! The explanation with images makes learning algorithm exciting and less frightening.

Here is a free version of breadth first algorithm. All the source code and images used in the book is available Github. The cool part is images are available under free for non-commercial use. If you're teaching algorithm, you can use them in your class!

The book has over 400 pictures and not a reference book but a good one to get started on algorithms.